#include <iostream>
using namespace std;

void qsort(double array[], int start, int end);
int  partition(double array[], int start, int end);
int main()
{
    double a[] = {0.1,0.8,0.1,1.0,2.0,0.1,0.65};
    int length = sizeof(a)/sizeof(a[0]);
    qsort(a,0,length-1);
    cout<< "the result of the sort:"<<endl;
    for(int i=0; i<length; ++i) {
        cout << a[i] << endl;
    }
}
void qsort(double array[], int start, int end)
{
    if(start >= end)return;
    int q = partition(array,start,end);
    qsort(array,start,q-1);
    qsort(array,q+1,end);
}

int partition(double  array[], int start,int end)
{
    if(start >= end) return start;
    if(start < 0) start = 0;
    int original  = start;
    double tmp = array[start];
    ++start;
    while(1) {
        while( start<=end && array[start] >= tmp)++start;
        while( start<=end && array[end] < tmp)--end;
        if(start < end) { 
            swap(array[start],array[end]);
        }
        else break;
    }
    swap(array[start-1],array[original]);
    return start-1;
}

void swap(double& a, double& b)
{
    double tmp = a;
    a = b;
    b = tmp;
}
